#1
# ls=[ ]
# while True:
#     s=input("")
#     if s=="Q":
#         break
#     flag =True
#     for c in s:
#         if c=="Q":
#             flag=False
#             break
#     if flag:
#         break
#     ls.append(c)
# print(ls)
# print("程序退出")
#3
# l=[1,2,3,4,5]
# print("列表的第十位：{}".format(l[10:]))
#8
# str="hello,wan neng de ce shi kai fa,wo shi zui  bang de ce shi gong cheng shi!"
# ct={}
# for i in str:
#     if i not in ct:
#         ct[i]=str.count(i)
# print(ct)
# print("0o1452")
# print(0x2a3e)
# list=[6,7,9,10,12,31,23,43,13]
# for i in range(len(list)):
#     for j in range(len(list)):
#         if list[i]>list[j]:
#             list[i],list[j]=list[j],list[i]
#11
# list=[6,7,9,10,12,31,23,43,13]
# for i in range(len(list)):
#     for j in range(i,len(list)):
#         if list[i]>list[j]:
#             list[i],list[j]=list[j],list[i]
# print(list)
#12
# s=""
# a=[1,3,6,9,8]
# b=[0,1,1,2,4,3,3,2,3,4,4,3]
# for i in b:
#     s=s+str(a[i])
# print(s)


#13
# str="we are ,we are rock you"
# ct={}
# for i in str:
#     if i not in ct:
#         ct[i]=str.count(i)
# print(ct)
#14
# def frog_days_to_escape(height,day_climb,night_slip):
#     current_height=0
#     days=0
#     while current_height<height:
#         days+=1
#         current_height+=day_climb
#         if current_height>=height:
#             break
#         current_height-=night_slip
#     return days
# height=10
# day_climb=2
# night_slip=2
# days=frog_days_to_escape(height,day_climb,night_slip)
# print("青蛙需要{}天才能爬出来。".format(days))
#15
# def max_soda_bottles(money,price_per_bottle,bottles_for_exchange):
#
#     bottles=money//price_per_bottle
#     empty_bottles=bottles
#     total_bottles=bottles
#     while empty_bottles>=bottles_for_exchange:
#         new_bottles=empty_bottles//bottles_for_exchange
#         total_bottles+=new_bottles
#         empty_bottles=empty_bottles%bottles_for_exchange+new_bottles
#     return total_bottles
# if __name__=='__main__':
#     height=10
#     day_climb=2
#     night_slip=1
#     days=frog_days_to_escape(height,day_climb,night_slip)

    # money = 40
    # price_per_bottle = 2
    # bottles_for_exchange = 2
    # bottle=frog_days_to_escape(height,day_climb,night_slip)
    # print("瓶子数目是:{}".format(bottle))
    # print("青蛙需要{}天才能爬出来。".format(days))




#88合并两个有序数组
# class Solution:
#     def merge(self, nums1, m: int, nums2, n: int) -> None:
#         p1 = m - 1
#         p2 = n - 1
#         p = m + n - 1
#
#         while p1 >= 0 and p2 >= 0:
#             if nums1[p1] > nums2[p2]:
#                 nums1[p] = nums1[p1]
#                 p1 -= 1
#             else:
#                 nums1[p] = nums2[p2]
#                 p2 -= 1
#             p -= 1
#
#         # 处理剩余nums2的元素
#         while p2 >= 0:
#             nums1[p] = nums2[p2]
#             p2 -= 1
#             p -= 1
#         return nums1
# if __name__ == '__main__':
#     solution = Solution()
#     nums=solution.merge([1,2,3,0,0,0],3,[2,5,6],3)
#     print(nums)
# def merge(nums1,m,nums2,n):
#     p1=m-1
#     p2=n-1
#     p=m+n-1
#     while p1>0 and p2>0:
#         if nums1[p1]>nums2[p2]:
#             nums1[p]=nums1[p1]
#             p1-=1
#         else:
#             nums1[p]=nums2[p2]
#             p2-=1
#         p-=1
#     while p2>0:
#          nums1[p]>nums2[p2]
#          p-=1
#          p2-=1
#     return nums1



#27移除元素
# def delete(nums,val):
#     slow=0
#     for fast in range(len(nums)):
#         if nums[fast]!=val:
#             nums[slow]=nums[fast]
#             slow+=1
#     return slow
# nums=[3,2,2,3]
# val=3
# k=delete(nums,val)
# print(k)
# def delete(nums,val):
#     slow=0
#     for fast in range(len(nums)):
#         if nums[fast] != val:
#             nums[slow]=nums[fast]
#             slow+=1
#     return nums
# nums=[3,2,2,3]
# val=3
# k=delete(nums,val)
# print(k)


#26删除有序数组中的重复项
# def delete(nums):
#    if not nums:
#        return 0
#    slow=0
#    for fast in range(1,len(nums)):
#         if nums[fast]!=nums[slow]:
#             slow+=1
#             nums[slow]=nums[fast]
#    return slow+1
# nums=delete([0,0,1,1,1,2,2,3,3,4])
# print(nums)
# def delete(nums):
#     if not nums:
#         return 0
#     slow=0
#     for fast in range(1,len(nums)):
#         if nums[fast] != nums[slow]:
#             slow+=1
#             nums[slow] = nums[fast]
#     return slow+1
# nums=delete([0,0,1,1,1,2,2,3,3,4])
# print(nums)


# #169多数元素
# def summ(nums):
#     count = 0
#     candidate=None
#     for num in nums:
#         if count==0:
#             candidate = num
#         else:
#             if num==candidate:
#               count += 1
#             else:
#               count-=1
#     return candidate
# can=summ([2,2,1,1,1,2,2])
# print(can)
# def sum(nums):
#     count = 0
#     candidate=None
#     for num in nums:
#         if count==0:
#             candidate = num
#         else:
#             if num==candidate:
#                 count += 1
#             else:
#                 count-=1
#     return candidate
# can=sum([2,2,1,1,1,2,2])
# print(can)

#80删除重复项
# def delete(nums):
#    if not nums:
#        return 0
#    slow=0
#    for fast in range(1,len(nums)):
#         if nums[fast]!=nums[slow]:
#             slow+=2
#             nums[slow]=nums[fast]
#    return slow+1
# nums=delete([1,1,1,2,2,3])
# print(nums)
# def delete(nums):
#     if not nums:
#         return 0
#     slow=2
#     for fast in range(2,len(nums)):
#         if nums[fast] != nums[slow-2]:
#             nums[slow]=nums[fast]
#             slow+=1
#     return slow
# nums=delete([1,1,1,2,2,3])
# print(nums)



# #189轮转数组
# def rotate(nums,k):
#     k=k%len(nums)
#     nums[:]=nums[-k:]+nums[:k]
#     return nums
# nums=[1,2,3,4,5,6,7]
# k=3
# print(rotate(nums,k))
# def rotate(nums,k):
#     k=k%len(nums)
#     nums[:]=nums[-k:]+nums[:k]
#     return nums
# nums=[1,2,3,4,5,6,7]
# k=3
# print(rotate(nums,k))


#121买卖股票的最佳时机
# def maxProfit(prices):
#     if not prices:
#         return 0
#     min_price=prices[0]
#     max_profit=0
#     for price in prices:
#         min_price=min(min_price,price)
#         current_profit=price-min_price
#         max_profit=max(max_profit,current_profit)
#     return max_profit
# prices=[7,1,5,3,6,4]
# print(maxProfit(prices))
# def maxProfit(prices):
#     if not prices:
#         return 0
#     min_price=prices[0]
#     max_profit=0
#     for price in prices:
#         min_price=min(min_price,price)
#         current_profit=price-min_price
#         max_profit=max(max_profit,current_profit)
#     return max_profit
# prices=[7,1,5,3,6,4]
# print(maxProfit(prices))

#122买卖股票的最佳时机2
# def maxProfit(prices):
#     profit = 0
#     for i in range(1, len(prices)):
#         if prices[i] > prices[i-1]:
#             profit += prices[i] - prices[i-1]
#     return profit
# # 示例测试
# prices =[7, 6, 4, 3, 1]
# print(maxProfit(prices))  # 输出: 7（1->5 + 3->6 的利润）
# def maxProfit(prices):
#     profit = 0
#     for i in range(1,len(prices)):
#         if prices[i] > prices[i-1]:
#             profit += prices[i] - prices[i-1]
#     return profit
# prices=[7,6,4,3,1]
# print(maxProfit(prices))

#55跳跃游戏
# def canjump(nums):
#     n=len(nums)
#     max_reach=0
#     for i in range(n):
#         if i>max_reach:
#             return False
#         max_reach=max(max_reach,i+nums[i])
#         if max_reach>=n-1:
#             return True
#     return False
# nums=[3,2,1,0,4]
# print(canjump(nums))
# def canjump(nums):
#     n=len(nums)
#     max_reach=0
#     for i in range(n):
#         if i>max_reach:
#             return False
#         max_reach=max(max_reach,nums[i]+i)
#         if max_reach>=n-1:
#             return True
#     return False
# nums=[3,2,1,0,4]
# print(canjump(nums))

#
# #跳跃游戏2
# def jump(nums):
#     n=len(nums)
#     if n==1:
#         return 0
#     jumps=0
#     current_end=0
#     farthest=0
#     for i in range(n-1):
#         farthest=max(farthest,i+nums[i])
#         if i==current_end:
#             jumps+=1
#             current_end=farthest
#             if current_end>=n-1:
#                 break
#     return jumps
# def jump(nums):
#     n=len(nums)
#     if n==1:
#         return 0
#     jumps=0
#     current_end=0
#     farthest=0
#     for i in range(n-1):
#         farthest=max(farthest,nums[i]+i)
#         if i==current_end:
#             jumps+=1
#             current_end=farthest
#             if current_end>=n-1:
#                 break
#     return jumps
#
#
#135分发糖果
# def candy(rating):
#     n=len(rating)
#     if n==0:
#         return 0
#     candies=[1]*n
#     for i in range(1,n):
#         if rating[i]>rating[i-1]:
#             candies[i]=candies[i-1]+1
#     for i in range(n-2,-1,-1):
#         if rating[i]>rating[i+1]:
#             candies[i]=max(candies[i],candies[i+1]+1)
#     return max(candies)



#134加油站
# def canCompleteCircuit(gas, cost):
#     total = 0
#     current = 0
#     start = 0
#     n = len(gas)
#
#     for i in range(n):
#         diff = gas[i] - cost[i]
#         total += diff
#         current += diff
#         if current < 0:
#             start = i + 1
#             current = 0
#
#     return start if total >= 0 else -1
# sum=canCompleteCircuit(gas = [1,2,3,4,5], cost = [3,4,5,1,2])
# print(sum)


#除自身以外数组的乘积
# def productExceptSelf(nums):
#     n=len(nums)
#     answer=[1]*n
#     for i in range(1,n):
#         answer[i]=nums[i-1]*answer[i-1]
#     right_product=1
#     for i in range(n-1,-1,-1):
#         answer[i]=answer[i]*right_product
#         right_product*=nums[i]
#     return answer
# answer=productExceptSelf([1,2,3,4])
# print(answer)




#时间插入、删除和获取随机数



#H指数
# def hIndex(citations):
#     citations.sort(reverse=True)
#     h = 0
#     for i in range(len(citations)):
#         if citations[i] >= i + 1:
#             h = i + 1
#         else:
#             break
#     return h
# h=hIndex([3,0,6,1,5])
# print(h)


# class Solution:
#     def trap(self, height: List[int]) -> int:
#         if not height:
#             return 0
#
#         left = 0
#         right = len(height) - 1
#         left_max = height[left]
#         right_max = height[right]
#         res = 0
#
#         while left < right:
#             if left_max < right_max:
#                 left += 1
#                 if height[left] > left_max:
#                     left_max = height[left]
#                 else:
#                     res += left_max - height[left]
#             else:
#                 right -= 1
#                 if height[right] > right_max:
#                     right_max = height[right]
#                 else:
#                     res += right_max - height[right]
#
#         return res
# def romanToInt(s: str) -> int:
#     mapping = {
#         'I': 1,
#         'V': 5,
#         'X': 10,
#         'L': 50,
#         'C': 100,
#         'D': 500,
#         'M': 1000
#     }
#     result = 0
#     i = 0
#     n = len(s)
#
#     while i < n:
#         if i < n - 1 and mapping[s[i]] < mapping[s[i + 1]]:
#             result += mapping[s[i + 1]] - mapping[s[i]]
#             i += 2
#         else:
#             result += mapping[s[i]]
#             i += 1
#     return result
# a=romanToInt("IV")
# print(a)


# def roman(s:str)->int:
#     roman_map = {
#         'I': 1,
#         'V': 5,
#         'X': 10,
#         'L': 50,
#         'C': 100,
#         'D': 500,
#         'M': 1000
#     }
#     total = 0
#     n=len(s)
#     for i in range(n):
#         if i<n-1 and roman_map[s[i]]<roman_map[s[i+1]]:
#             total-=roman_map[s[i]]
#         else:
#             total+=roman_map[s[i]]
#     return total
#
# total=roman("LVIII")
# print(total)

#最后一个单词的长度
# def lastword(s:str)->int:
#     n=len(s)
#     count=0
#     for i in range(n-1,-1,-1):
#         if s[i]==" ":
#             if count>0:
#                 return count
#         else:
#             count+=1
#     return count
# sum=lastword("Hello World")
# print(sum)

# #最长公共前缀
# def longest(strs)->int:
#     if not strs:
#         return 0
#     for i in range(len(strs[0])):
#         s=strs[0][i]
#         for j in range(1,len(strs)):
#             if i>len(strs[j]) or strs[j][i]!=s:
#                 return strs[0][:i]
#     return strs[0]
# strs = ["flower","flow","flight"]
# s=longest(strs)
# print(s)


#反转字符串中的单词
# def reversewords(s:str)->str:
#     words = s.split()
#     return ' '.join(reversed(words))
# s=reversewords("the sky is blue")
# print(s)

#Z字形变换
# def convert(s: str, numRows: int) -> str:
#         if numRows == 1:
#             return s
#
#         T = 2 * numRows - 2  # 周期长度
#         rows = [''] * numRows  # 初始化每行字符串
#
#         for i, char in enumerate(s):
#             pos = i % T  # 当前字符在周期中的位置
#             # 确定字符应放入的行
#             if pos < numRows:
#                 rows[pos] += char
#             else:
#                 rows[T - pos] += char
#
#         return ''.join(rows)  # 拼接所有行
# str=convert("PAYPALISHIRING",3)
# print(str)


#找出字符串中第一个匹配项的下标
# def strStr(self,haystack:str,needle:str)->int:
#     n=len(haystack)
#     m=len(needle)
#     if m==0:
#         return 0
#     for i in range(n-m+1):
#         if haystack[i:i+m]==needle:
#             return i
#     return -1


#判断子序列
# def isSubsequence(s:str,t:str):
#     i=0
#     j=0
#     while i<len(s) and j<len(t):
#         if s[i]==t[j]:
#             i+=1
#         j+=1
#     return i==len(s)
#
# a=isSubsequence("abc","ahbgdc")
# print(a)


#验证回文串
# def isPalindrome(s:str)->bool:
#     cleaned =''.join(char.lower() for char in s if char.isalnum())
#     left.right=0,len(cleaned)-1
#     while left < right:
#         if cleaned[left] != cleaned[right]:
#             return False
#         left+=1
#         right-=1
#     return True


#整数转罗马数字
# def intToroman(num:int)->str:
#     if not 1<=num<=3999:
#         raise ValueError("输入整数必须在1到3999之间")
#     values=[1000,900,500,400,100,90,50,40,10,9,5,4,1]
#     symbols=["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"]
#     result=[]
#     for value,symbol in zip(values,symbols):
#         while num>=value:
#             num-=value
#             result.append(symbol)
#         if num==0:
#             break
#     return "".join(result)
# char=intToroman(3749)
# print(char)



#长度最小的子数组
# def minSubArraylen(target,nums)->int:
#     n=len(nums)
#     left=0
#     current_sum=0
#     min_length=0
#     for right in range(n):
#         current_sum+=nums[right]
#         while current_sum>=target:
#             min_length=min(min_length,right-left+1)
#             current_sum-=nums[left]
#             left+=1
#     return min_length
# min=minSubArraylen(7,[2,3,1,2,4,3])
# print(min)

#三数之和
# def threesum(nums):
#     nums.sort()
#     result = []
#     n=len(nums)
#     if nums==0:
#         return 0
#     for i in range(n):
#         if nums[1]>0:
#             return 0
#         left=i+1
#         right=n-1
#         while left<right:
#             sum=nums[i]+nums[left]+nums[right]
#             if sum<0:
#                 left+=1
#             elif sum>0:
#                 right-=1
#             else:
#                 result.append([nums[left],nums[right],nums[i]])
#                 while left<right and nums[left]==nums[left+1]:
#                     left+=1
#                 while right<left and nums[right]==nums[right-1]:
#                     right-=1
#             left+=1
#             right-=1
#     return result
# result=threesum([-1,0,1,2,-1,-4])
# print(result)


#盛最多水的容器
# def maxArea(height):
#     left=0
#     right=len(height)-1
#     max_water=0
#     while left<right:
#         width=right-left
#         current_height=min(height[left],height[right])
#         current_water=width*current_height
#         if current_water>max_water:
#             max_water=current_water
#         if height[left]<height[right]:
#             left=left+1
#         else:
#             right=right-1
#     return max_water
# max=maxArea([1,8,6,2,5,4,8,3,7])
# print(max)


#两数之和-输入有序数组
# def twosum(target,nums):
#     nums.sort()
#     n=len(nums)
#     result=[]
#     right=n-1
#     left=0
#     while left<right:
#       if nums[right]+nums[left]==target:
#         return [left+1,right+1]
#       elif nums[right]+nums[left]>target:
#         right-=1
#       else:
#         left+=1
#     return 0
# result=twosum(9,[2,7,11,15])
# print(result)



#文本左右对齐
def fulljustify(words,maxWidth):
    result = []
    current_line=[]//当前行单词
    current_length=0//当前行单词总长度
    for word in words:
        required_length=current_length+len(word)+len(current_line)
        if required_length<=maxWidth:
            current_line.append(word)
            current_length+=len(word)
        else:
            if len(current_line)==1:
                formatted_line=current_line[0]+" "*(maxWidth-current_length)
            else:
                total_spaces=maxWidth-current_length
                num_gaps=len(current_line)-1
                base_spaces=total_spaces//num_gaps
                extra_spaces=total_spaces%num_gaps
                formatted_line=current_line[0]
                for i in range(1,len(current_line)):
                    spaces=base_spaces+(1 if i <=extra_spaces else 0)
                    formatted_line+=" "*spaces+current_line[i]
            result.append(formatted_line)
            current_line=[word]
            current_length=len(word)
    if current_line:
        last_line=" ".join(current_line)
        last_line+=" "*(maxWidth-current_length)
        result.append(last_line)
    return result